import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class project {
    public int maxDistance(int[] nums1, int[] nums2) {
        int len1=nums1.length;
        int len2=nums2.length;
        int sum=0;
        int i=0;
        for(int j=0;j<len2;j++){
            if(i<len1&&nums1[i]>nums2[j]){
                i++;
            }
            if(i<len1){
                sum=Math.max(sum,j-i);
            }
        }
        return sum;
    }














    public int maxSumAfterPartitioning(int[] arr, int k) {
        int sum=0;
        int remainder=arr.length%k;
        int divisor=arr.length/k;
        Arrays.sort(arr);
        int i=arr.length-1;
        while (divisor>0){
            for(int j=0;j<k;j++){
                sum+=arr[i];
            }
            i--;
            divisor--;
        }
        for(int j=0;j<remainder;j++){
            sum+=arr[i];
        }
        return sum;
    }












    public List<String> letterCasePermutation(String s) {
        List<String> list=new ArrayList<>();
        dfs(0,new StringBuilder(s),list);
        return list;
    }
    public void dfs(int start,StringBuilder str,List<String> list){
        if(start==str.length()){
            list.add(new String(str));
            return;
        }
        char ch=str.charAt(start);
        dfs(start+1,str,list);
        if((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')){
            if(ch<='Z'){
                str.setCharAt(start,(char)(ch+32));
            }else{
                str.setCharAt(start,(char)(ch-32));
            }
            dfs(start+1,str,list);
        }
    }




















    public int lastRemaining(int n) {
        int start=1;
        int step=1;
        boolean bool=true;
        while (n>1){
            if(bool||n%2!=0){
                step+=start;
            }
            start*=2;
            n/=2;
            bool=!bool;
        }
        return step;
    }
}
